COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00005 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\baselineskip 14pt
\line{\sevenrm a10.tex[154,mps] \today\hfill}
\parskip 6pt
\bigskip
\noindent{\bf Theorem.}
There are inherently ambiguous context-free languages.

\medskip\noindent
{\bf Proof.} Such a language is 
$$L=\{a↑ib↑ic↑j\}∪\{a↑ib↑jc↑j\}\,.$$
Let $G$ be any CFG for $L$.  Let $T↓1=\{b\}$, $T↓0=\{a,c\}$.  Ogden's lemma
gives a number $n$, which we may select  to be at least 3.  
Let $z=a↑nb↑nc↑{n+n!}$.
Then the only way to pump is for
$z=uvwxy$, where $v=a↑k$, $x=b↑k$, $k≤n$. Since $k$ divides~$n!$,
by pumping $n!/k$ times, we get a derivation of 
$a↑{n+n!}b↑{n+n!}c↑{n+n!}$, where there is a phrase including
at least $n!$~each of~$a$'s and~$b$'s, and no~$c$'s.

Now do the same to pump $z=a↑{n+n!}b↑nc↑n$, getting a derivation of
$a↑{n+n!}b↑{n+n!}c↑{n+n!}$ with a phrase including at least $n!$~each
of $b$'s and~$c$'s, and no~$a$'s.

The two phrases overlap (because $n≥3$), but neither is a substring
of the other. They must therefore belong to distinct derivations,
$a↑{n+n!}b↑{n+n!}c↑{n+n!}$ is ambiguous, every grammar for~$L$
is ambiguous, $L$~is inherently ambiguous, and $L$~is not a~DCFL.

Ogden's theorem is commonly called Ogden's lemma because it was introduced
as a lemma to prove the above result
\bigskip
\noindent References: Gross 1964, Ginsburg and Ullian 1966, a \&\ b.

\bigskip
\noindent\copyright Robert W. Floyd, May 9, 1988
\end